package project3;

import edu.princeton.cs.algs4.Edge;
import edu.princeton.cs.algs4.EdgeWeightedGraph;
import edu.princeton.cs.algs4.In;
import project3.dijkstra.DijkstraSp1;
import project3.dijkstra.DijkstraSp1_2;

import java.io.File;
import java.util.Scanner;
import edu.princeton.cs.algs4.Stack;

/**
 * 任意点对之间的距离,打印最短路径
 * */
public class Path {

    public static void display(Stack<Edge> stack,int s){
        Edge edge = stack.pop();
        int v = edge.other(s);
        System.out.print(s+" -> "+v);
        while (!stack.isEmpty()){
            Edge tempEdge = stack.pop();
            int w = tempEdge.other(v);
            System.out.print(" -> "+w);
            v = w;
        }
        System.out.println();
    }

    public static void findRoute1(EdgeWeightedGraph mDigraph,
                                 Point[] points,int s,int d){
        System.out.println("优化前：");
        DijkstraSp1 msp = new DijkstraSp1(mDigraph,points);
        long start_time = System.currentTimeMillis();
        msp.setFrom(s);
        msp.setTo(d);
        boolean b = msp.hasPathTo(d);
        if (b) {
            long consumingtime=System.currentTimeMillis()-start_time;
            System.out.println("运行时间："+consumingtime+"ms");
                //double distences = 0;
            System.out.println("最短路径为：");
            Stack<Edge> stack = msp.pathTo(d);
            display(stack, s);
        } else {
            long consumingtime=System.currentTimeMillis()-start_time;
            System.out.println("运行时间："+consumingtime+"ms");
            System.out.println("不存在一条路径");
            System.out.println();
        }

    }
    public static void findRoute2(EdgeWeightedGraph mDigraph,
                                  Point[] points,int s,int d){

        System.out.println("优化后：");
        DijkstraSp1_2 msp = new DijkstraSp1_2(mDigraph,points);
            long start_time = System.currentTimeMillis();
            msp.setFrom(s);
            msp.setTo(d);
            boolean b = msp.hasPathTo(d);
            if (b) {
                long consumingtime=System.currentTimeMillis()-start_time;
                System.out.println("运行时间："+consumingtime+"ms");
                //double distences = 0;
                System.out.println("最短路径为：");
                Stack<Edge> stack = msp.pathTo(d);
                display(stack, s);
            } else {
                long consumingtime=System.currentTimeMillis()-start_time;
                System.out.println("运行时间："+consumingtime+"ms");
                System.out.println("不存在一条路径");
                System.out.println();
        }

    }


    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        Test3 test3 = new Test3();
        File file = new File("D:/my_code/Algorithm4/AlgorithmHomework/resources/usa.txt");
        In in = new In(file);
        int a = in.readInt();
        int b = in.readInt();
        EdgeWeightedGraph mDigraph = new EdgeWeightedGraph(a);
        Point[] points = new Point[a];
        test3.init_Point(in, points);
        test3.init_Graph(in, b, mDigraph, points);
        int n = 10;
        while (n>=0) {
            int s = scanner.nextInt();
            int d = scanner.nextInt();
            findRoute1(mDigraph, points, s, d);
            findRoute2(mDigraph, points, s, d);
            n--;
        }
    }
}
